package com.stropheware.pathfinding;

import java.util.ArrayList;

import com.stropheware.droidDefense.GameBoard;

import android.util.Log;


public class PathFinder {
	
	private final static String TAG = "PathFinder";
	
	/** The set of nodes that we do not yet consider fully searched 
	 *  Needs to be sorted */
	private static SortedList open = new SortedList();
	
	/** The map being searched, this will be gameBoard */
	private static GameBoard gameBoard;
	/** The maximum depth of search we're willing to accept before giving up */
	private int maxSearchDistance;
	
	/** The complete set of nodes across the map */
	public static Node[][] nodes;
	/** True if we allow diaganol movement */
	private boolean allowDiagMovement;
	
	private static Path path;
	
		
	
	/**
	 * Create a path finder 
	 * 
	 * @param heuristic The heuristic used to determine the search order of the map
	 * @param map The map to be searched
	 * @param maxSearchDistance The maximum depth we'll search before giving up
	 * @param allowDiagMovement True if the search should try diaganol movement
	 */
	public PathFinder(GameBoard gameboard, int maxSearchDistance, boolean allowDiagMovement) {
		this.gameBoard = gameboard;
		this.maxSearchDistance = maxSearchDistance;
		this.allowDiagMovement = allowDiagMovement;
				
		boolean tempIsTop;
		boolean tempIsEdge;

		nodes = new Node[gameBoard.getNodesWidth()][gameBoard.getNodesHigh()];
		Log.d("PathFinder ", "Nodes wide = "+ gameBoard.getNodesWidth() + " Nodes High: " + gameBoard.getNodesHigh());
		for (int x=0;x<gameBoard.getNodesWidth();x++) {
			for (int y=0;y<gameBoard.getNodesHigh();y++) {
				nodes[x][y] = new Node(x,y,gameBoard);
			}
		}
		path = new Path();
	}
	
	/**
	 * @param s start Node
	 * @param t target Node
	 * @return
	 */
	public Path findPath(Node s, Node t, GameBoard curGameBoard) {
				
		// initial state for A*. The closed group is empty. Only the starting
		// tile is in the open list and it's cost is zero, i.e. we're already there
		nodes[s.indexX][s.indexY].cost = 0;
		nodes[s.indexX][s.indexY].depth = 0;
		resetVisitedNodes();
		open.clear();
		open.add(nodes[s.indexX][s.indexY]);
		
		nodes[t.indexX][t.indexY].parent = null;
		
		// while we haven't found the goal and haven't exceeded our max search depth
		int maxDepth = 0;
		while ((maxDepth < maxSearchDistance) && (open.size() != 0)) {
			// pull out the first node in our open list, this is determined to 
			// be the most likely to be the next step based on our heuristic
			Node current = open.first();
			if (current == nodes[t.indexX][t.indexY]) {
				break;
			}
			
			//removeFromOpen(current)
			open.remove(current);
			//addToClosed(current);
			current.visited = true; //closed.add(current);
			
			
			// search through all the neighbours of the current node evaluating
			// them as next steps
			for (int x=-1;x<2;x++) { //don't look back implementation
				for (int y=-1;y<2;y++) {
					// not a neighbour, its the current tile
					if ((x == 0) && (y == 0)) {
						continue;
					}
					
					// if we're not allowing diaganol movement then only 
					// one of x or y can be set
					if (!allowDiagMovement) {
						if ((x != 0) && (y != 0)) {
							continue;
						}
					}
					
					// determine the location of the neighbour and evaluate it
					int xp = x + current.indexX;
					int yp = y + current.indexY;
										
					if (isValidLocation(current,xp,yp)) {
						// the cost to get to this node is cost the current plus the movement
						// cost to reach this node. Note that the heursitic value is only used
						// in the sorted open list
						int nextStepCost = current.cost + 1;
						//int nextStepCost = (int) (current.cost + getHeuristicCost(nodes[xp][yp], t));
						Node neighbour = nodes[xp][yp];
						//pathFinderVisited(neighbour);
						
						// if the new cost we've determined for this node is lower than 
						// it has been previously makes sure the node hasn't been discarded. We've
						// determined that there might have been a better path to get to
						// this node so it needs to be re-evaluated
						if (nextStepCost < neighbour.cost) {
							if (open.contains(neighbour)) {
								open.remove(neighbour);
							}
							/*if (closed.contains(neighbour)) {
								closed.remove(neighbour);
							}*/
							if(neighbour.visited) neighbour.visited = false;
						}
						
						// if the node hasn't already been processed and discarded then
						// reset it's cost to our current cost and add it as a next possible
						// step (i.e. to the open list)
						/*if (!inOpenList(neighbour) && !(inClosedList(neighbour))) {
							neighbour.cost = nextStepCost;
							neighbour.heuristic = getHeuristicCost(mover, xp, yp, tx, ty);
							maxDepth = Math.max(maxDepth, neighbour.setParent(current));
							addToOpen(neighbour);
						}*/
						//if (!open.contains(neighbour) && !(closed.contains(neighbour))) {
						if (!open.contains(neighbour) && !(neighbour.visited)) {
							neighbour.cost = nextStepCost;
							neighbour.heuristic = getHeuristicCost(neighbour, t);
							maxDepth = Math.max(maxDepth, neighbour.setParent(current));
							open.add(neighbour);
						}
					}
				}
			}
		}

		// since we've got an empty open list or we've run out of search 
		// there was no path. Just return null
		if (nodes[t.indexX][t.indexY].parent == null) {
			return null;
		}
		
		// At this point we've definitely found a path so we can uses the parent
		// references of the nodes to find out way from the target location back
		// to the start recording the nodes on the way.
		path.steps.clear();
		Node target = nodes[t.indexX][t.indexY];
		while (target != nodes[s.indexX][s.indexY]) {
			path.prependStep(target.indexX, target.indexY);
			target = target.parent;
		}
		path.prependStep(s.indexX,s.indexY);
		
		// thats it, we have our path 
		return path;
	}
	
	private boolean isValidLocation(Node s, int x, int y) {
		boolean invalid = (x < 0) || (y < 0) || (x >= gameBoard.getNodesWidth()) || (y >= gameBoard.getNodesHigh());
		
		if ((!invalid) && ((s.indexX != x) || (s.indexY != y))) {
			invalid = nodes[x][y].containsTower();
		}
		return !invalid;
	}
	
	private void resetVisitedNodes() {
		for (int x=0;x<gameBoard.getNodesWidth();x++) {
			for (int y=0;y<gameBoard.getNodesHigh();y++) {
				nodes[x][y].visited = false;
			}
		}
	}
	
	/* manhattan distance heuristic*/
	public int getHeuristicCost(Node neighbor, Node target) {	
		int dx = Math.abs(target.indexX - neighbor.indexX);
	    int dy = Math.abs(target.indexY - neighbor.indexY);
	    return dx+dy;	
	}
	
	/*
	 * get nearest cell given x,y in pixels
	 */
	public static Node getNearestNode(int x, int y) {
		x -= gameBoard.startXPixel; //TODO is this right?
		y -= gameBoard.startYPixel;
		try {
			return nodes[x / gameBoard.cellSideLength][y / gameBoard.cellSideLength]; //TODO
		}catch (ArrayIndexOutOfBoundsException e) {return null;}
	}
}
